// 图-邻接表
#ifndef GRAPH_ADLIST_H
#define GRAPH_ADLIST_H

// 最大顶点数
#ifndef MAX_VEX
#define MAX_VEX 100
#endif

/// @brief 边表节点
typedef struct EdgeNode
{
	int adjvex;			   // 邻接点下标
	int weight;			   // 边权值
	struct EdgeNode *next; // 下一个边节点
} EdgeNode;

/// @brief 顶点表节点
typedef struct
{
	int in;				 // 这个顶点的入度（拓扑排序用）
	char data;			 // 数据
	EdgeNode *firstEdge; // 第一个边的边表指针
} VertexNode;

/// @brief 邻接表
typedef struct
{
	VertexNode vertexs[MAX_VEX]; // 存放所有顶点的顶点表
	int vertexNum, edgeNum;		 // 顶点个数，边个数
} GraphAdList, *AdList;

/// @brief 初始化一个邻接表对象
/// @return 邻接表对象指针
AdList createAdList();

/// @brief 查找邻接表中的一个点的位置
/// @param adList 传入邻接表的指针
/// @param v 查找顶点v在顶点表的下标
/// @return v的下标，点不存在返回-1
int adListLocateVex(AdList, char);

/// @brief 查找邻接表中顶点v的第一个邻接点
/// @param adList 传入邻接表的指针
/// @param v 顶点v的下标
/// @return 顶点v的邻接点的下标，没有邻接点返回-1
int adListFirstAdjVex(AdList, int);

/// @brief 插入一个顶点
/// @param adList 传入邻接表的指针
/// @param v 插入顶点的值
void adListInsertVex(AdList, char);

/// @brief 插入一条弧
/// @param adList 传入邻接表的指针
/// @param v 弧的起点下标
/// @param w 弧的终点下标
/// @param weight 弧的权值
void adListInsertArc(AdList, int, int, int);

/// @brief 深度优先遍历并输出-递归部分
/// @param adList 传入邻接表的指针
/// @param start 遍历起始点
/// @param visit 辅助数组记录已访问的点
void adListDFS(AdList, int, int[]);

/// @brief 深度优先遍历
/// @param adList 传入邻接表的指针
void adListDFSTraverse(AdList);

/// @brief 广度优先遍历
/// @param adList 传入邻接表的指针
void adListBFSTraverse(AdList);

/// @brief 打印邻接表
/// @param adList 传入邻接表的指针
void printAdList(AdList);

#include "./ad-list.c"

#endif